#include "Multitree.h"
#include "Tuplets.h"
namespace SymCe{
/*	Multitree * add_and_multiply(Multitree * tree){

		//Adds terms that can be simply added, multiplies terms that
		//can be simply multiplied.
		LATER.
	}
*/

	Multitree * give_me_empty_tree(){
		return new Multitree;
	}


	int treecmp(Multitree * first, Multitree * second){
		//If the symbols are different, then decide according to the symbols. 
		if (first->symbol < second->symbol){
			return -1;
		}
		if (!(first->symbol == second->symbol)){
			return 1;
		}
		ListOfChilds * left;
		ListOfChilds * right;
		left = first->childs;
		right = second->childs;
		while(true){
			if((left == NULL) && (right ==NULL)){
				return 0; //They are same
			}
			if (right == NULL){
				return -1; //Let the one with less sons be smaller
			}

			if (left == NULL){
				return 1;
			}

			int tmp = treecmp(left->subtree, right->subtree);

			if(tmp != 0){
				return tmp;
			}

			if(left->inverted != right->inverted){
				//inverted is "larger"
				return right->inverted;
			}
			left=left->next;
			right = right->next;
		}
	}

	


	Multitree * copy_tree(Multitree * tree){
		if (tree == NULL){
			return NULL;
		}
		Multitree * copy = new Multitree;
		copy->symbol = tree->symbol;
		copy->childs = NULL;
		if(tree->childs == NULL){
			//it was leaf
			return copy;
		}
		//Now we copy sons, one by one.
		ListOfChilds * added; //We add after this to new tree
		ListOfChilds * pass; //Going through tree.
		pass = tree->childs;
		added = new ListOfChilds;
		added->inverted = pass->inverted;
		added->next=NULL;
		added->subtree = copy_tree(pass->subtree);
		copy->childs = added;
		pass = pass->next;
		while(pass != NULL){
			//repeat
			added->next = new ListOfChilds;
			added->next->inverted = pass->inverted;
			added->next->next = NULL;
			added->next->subtree = copy_tree(pass->subtree);
			added = added->next;
			pass = pass->next;
		}
		return copy;
	}


	void delete_list(ListOfChilds * childs){
		ListOfChilds * next = NULL;
		while(childs !=NULL){
			next = childs->next;
			delete childs;
			childs = next;
		}
	}


/*	void delete_list(ListOfChilds * childs){
		if(childs == NULL){
			return;
		}
		delete_list(childs->next);
		delete childs;
	}
*/		
	void delete_childs(ListOfChilds * childs){
		ListOfChilds * pass = childs;
		while(pass != NULL){
			delete_tree(pass->subtree);
			pass = pass->next;
		}
		delete_list(childs);
	}


	void delete_tree(Multitree * tree){
		if(tree == NULL){
			return;
		}
		ListOfChilds * child = tree->childs;
		while(child != NULL){
			delete_tree(child->subtree);
			child = child->next;
		}
		delete_list(tree->childs);
		delete tree;
	}


	std::ostream & output_tree(Multitree * tree, std::ostream & stream){
		ListOfChilds * childs = tree->childs;
		switch(tree->symbol.type){
			case CONSTANT:
			case VARIABLE:
				return stream << tree->symbol.name;
				break;
			case NUMBER:
				return stream << tree->symbol.number;
				break;
			case FUNCTION:
				//TODO: (cos(x))^2 and cos(x^2) are outputed in the same way. It should not be so.
				switch (tree->symbol.func){
					case COS:
						stream << "cos ";
						break;
					case SIN:
						stream << "sin ";
						break;
					case TAN:
						stream << "tan ";
						break;
					case LN:
						stream << "ln ";
						break;
					default:
						stream <<"???";
				}
				//We have one argument, so print it.
				return output_tree(tree->childs->subtree, stream);
				break;
			case OPERATOR:
				//We should (probably) output parentheses around this.
				stream << '(';
				
				//TODO: Do not output 0 - here

				if (childs->inverted){
					//Tree can be multiply or plus
					if (tree->symbol.oper == MULTIPLY){
						stream << "1/";
					}else{
						stream << "-";
					}
				}
				output_tree(childs->subtree, stream);
				char op;
				char inop;
				switch(tree->symbol.oper){
					case PLUS:
						op = '+';
						inop = '-';
						break;
					case MULTIPLY:
						op = '*';
						inop = '/';
						break;
					case POWER:
						op = '^';
						inop = '?';
						break;
				}
				childs = childs->next;
				while (childs != NULL){
					if (childs->inverted){
						stream << inop;
					}else{
						stream << op;
					}
					output_tree(childs->subtree, stream);
					childs=childs->next;
				}
				return stream << ')';
				break;
			default:
				return stream << "??";
		}
	}

	void invert_childs(ListOfChilds * childs){
		while(childs != NULL){
			childs->inverted = !(childs->inverted);
			childs = childs->next;
		}
	}

	void rehang_tree(Multitree * tree){
		//Rehang all sons and then rehang this tree, if applicable (+ or *)
		//Can we do it in place? Yes. And we never change tree pointer (that is passed by value).
		switch(tree->symbol.type){
			case NUMBER:
			case CONSTANT:
			case VARIABLE:
				//We have nothing to do. There are no subtrees.
				return;
			case FUNCTION:
				//Just rehang argument.
				rehang_tree(tree->childs->subtree);
				return;
			case OPERATOR:
				//First, rehang all sons.
				ListOfChilds * pass = tree->childs;
				while (pass != NULL){
					rehang_tree(pass->subtree);
					pass = pass->next;
				}
				if(tree->symbol.oper == POWER){ //We do not rehang anything else.
					return;
				}
				//Now we divide list of sons to compatible and others.
				//We completely disintegrate list of childs!
				ListOfChilds * compatible = NULL;
				ListOfChilds * others = NULL;
				ListOfChilds * following = NULL;
				pass = tree->childs;
				while (pass != NULL){
					following = pass->next;
					if (pass->subtree->symbol == tree->symbol){
						pass->next = compatible;
						compatible = pass;
					}else{
						pass->next = others;
						others = pass;
					}
					pass = following;
				}
				//childs are divided to two strings.
				tree->childs = others; //Others can be immediately added to tree;
				//Now we pass through compatible and add their subtrees to tree->child.
				
				ListOfChilds * end = tree->childs;
				if (end == NULL){ //No incompatible childs.
					//Take first compatible and attach it's childs to tree.
					tree->childs = compatible->subtree->childs;
					if(compatible->inverted){ //invert, if necessary
						invert_childs(tree->childs);
					}
					following = compatible->next;
					delete compatible->subtree;
					delete compatible;
					compatible = following;
					end = tree->childs;
				}

				while (end->next != NULL){
					end = end->next;
				}

				pass = compatible;

				while(pass != NULL){
					following = pass->next;
					if(pass->inverted){
						invert_childs(pass->subtree->childs);
					}
					//Now just insert pass->subtree->childs to tree->childs. (how?)
					end->next = pass->subtree->childs;
					while (end->next != NULL){
						end = end->next;
					}
					delete pass->subtree;
					delete pass;
					pass = following;
				}//Should be all.
				return;
		}
	}

	void sort_tree(Multitree * tree){
		switch (tree->symbol.type){
			case CONSTANT:
			case NUMBER:
			case VARIABLE:
				return;
				break;
			case FUNCTION:
				sort_tree(tree->childs->subtree);
				return;
				break;
			case OPERATOR:
				ListOfChilds * pass = tree->childs;
				while (pass != NULL){
					sort_tree(pass->subtree);
					pass = pass->next;
				}
				if (tree->symbol.oper == POWER){
					return;
					break;
				}
				//Let's sort.
				ListOfChilds * from = tree->childs;
				Multitree * tmp;
				bool inv;
				ListOfChilds * min;
				int cmp;
				while (from != NULL){
					pass = from->next;
					min = from;
					while (pass != NULL){
						cmp = treecmp(pass->subtree, min->subtree);
						if((cmp == 0)&& (min->inverted != pass->inverted)){//same trees but not same inverted.
							cmp = pass->inverted == false?-1:1; //if pass is not inverted, it is smaller.
						}
						if (cmp < 0){
							min = pass;
						}
						pass = pass->next;
					}
					if(min != from){
						//exchange their content
						tmp = from->subtree;
						inv = from->inverted;
						from->subtree = min->subtree;
						from->inverted = min->inverted;
						min->inverted = inv;
						min->subtree = tmp;
						tmp = NULL;
					}
					from = from->next;
				}
		}
	}



	bool is_number(Multitree * tree, Number number){
		if((tree->symbol.type == NUMBER) && (tree->symbol.number == number)){
			return true;
		}else{
			return false;
		}
	}

	Multitree * replace_variable_tree(Multitree * original, char * variable, Multitree * with){
		if(original == NULL){
			return NULL;
		}
		//Replaces variable in the original tree with "with" tree.
		if ((original->symbol.type == VARIABLE)
			&& (strcmp(original->symbol.name, variable) == 0)){
				return copy_tree(with);
		}else{
			//very similar to copy_tree
			//in fact, it is copied from copy_tree.
			Multitree * to_return  = new Multitree;
			to_return->symbol = original->symbol;
			to_return->childs = NULL;
			if(original->childs == NULL){
				return to_return;
			}

			ListOfChilds * added;
			ListOfChilds * pass;
			pass = original->childs;
			added = new ListOfChilds;
			added->inverted = pass->inverted;
			added->next=NULL;
			added->subtree = replace_variable_tree(pass->subtree, variable, with);
			to_return->childs = added;
			pass = pass->next;
			while(pass != NULL){
				added->next = new ListOfChilds;
				added->next->inverted = pass->inverted;
				added->next->next = NULL;
				added->next->subtree = replace_variable_tree(pass->subtree, variable, with);
				added = added->next;
				pass = pass->next;
			}
			return to_return;
		}
	}

	ListOfChilds * give_me_empty_child(){
		return new ListOfChilds;
	}

	Multitree * give_me_tree_with_two_childs(){
		//creates an empty structure - tree with two childs - but returned tree is correct
		//we do not want incorrect tree leaving our functions
		//this piece of code is written too often through the functions - everywhere
		//where we need a new tree - practically in every function.
		Multitree * tree = give_me_empty_tree();
		tree->symbol.type = OPERATOR; //only operator has more than one child.
		tree->symbol.oper = PLUS;	//plus can hold anything (no fear of zeros)
		tree->childs = give_me_empty_child();
		tree->childs->next = give_me_empty_child();
		tree->childs->next->next = NULL;
		tree->childs->next->inverted = false;
		tree->childs->next->subtree = give_me_empty_tree();
		tree->childs->next->subtree->symbol.type = NUMBER; //make it something without childs - this can be changed later, if necessary
		//However there can be a problem - these subtrees need to be deleted when creating new tree!
		tree->childs->next->subtree->childs = NULL;
		tree->childs->inverted = false;
		tree->childs->subtree = give_me_empty_tree();
		tree->childs->subtree->symbol.type = NUMBER;
		tree->childs->subtree->childs = NULL;
		return tree;
	}





		

}

